.xgp
.FONT 0 30VR
.FONT 1 30VRI
.FONT 2 37VRB
.FONT 3 S30GRK
.squish
.script 5
.tabfnt 0
.adjust
.twinch 6.0
.he1
Convergence of cooperative algorithms
.he2
∞
.sp 3
.center
ε2ON THE CONVERGENCE OF xε0(n + 1)ε2↔ = ε3sε2{L(xε0(n)ε2↔)⎇
.sp 2
.center
by
.sp 2
.center
D. Marr
.sp 4
.center
Draft Iε0
.sp 6
.single
ε1Summaryε0. 
.pa
.double
.center
ε2Introductionε0
	The implementation of Marr & Poggio's (1976a) method for determining
stereoscopic disparity from an image pair was achieved by using what they
called a cooperative algorithm. Although the class of such algorithms is
not precisely definable, one of their essential features is that
they operate on many "input" elements, and reach a global organization ε1viaε0
local but highly interactive constraints (Marr & Poggio 1976b). They
were called cooperative algorithms by analogy with cooperative phenomena
in physics (see e.g. Haken 1975), and display all the qualitative
phenomena found there -- bifurcations and phase transitions, hysteresis,
"filling in" and the absence of a characteristic "scale".
	The analysis of cooperative phenomena in physics is extremely
difficult. The three-dimensional Ising problem has still not been
resolved (ref). When one designs a cooperative algorithm, however, one
has an important extra piece of knowledge that helps one to analyze the
behavior of the algorithm, and which is not usually available in
physical situations. That extra information is knowledge about the
ε1goalε0 of the computation, usually represented as constraints on its
stable states. When designing a computation, one knows what the goal is,
and designs the local constraints appropriately, whereas in a physical
problem, the nature of the local interactions is given, and the problem
is to determine the system's stable states.
	Despite this additional help, it is not easy to establish
general results about the convergence of cooperative algorithms. The
example studied by Marr & Poggio (1976a) had the form
.center
.nofill
ε1x(n + 1)↔ = ε3sε1{L(x(n)↔)⎇ε0                    (1)
.br
.adjust
where ε1x(n)↔ε0 denotes the state at time ε1(n)ε0,
ε1Lε0 is a linear operator, and ε3sε0 is a sigmoid or threshold function.
The constraints are embedded in the linear operator ε1Lε0, according
to the rule that nodes which should be "on" together in the final state
should send positive or "excitatory" signals to one another, and nodes
that are incompatible should be mutually "inhibitory". Figure 1 shows the
local interaction geometry for two examples. Figure 1a illustrates the constraints for
solving the correspondence problem for stereo disparity, and figure 1b
illustrates the constraints for finding a continuous vector field in an
image. Marr (1971) gave an algorithm of this form for solving the best
match retrieval problem in an associative memory.
	In all these cases, one can easily see that the desired goal of
the computation is a stable state of the algorithm designed for it, but
it is usually much more difficult to establish that the algorithm
converges to this state. Marr (1971) and Marr & Poggio (1976) used a
combinatorial argument, but it relied upon a precise knowledge of the
structure of the algorithm. Nevertheless, in both these cases it was
found that the exact form of the algorithm was rather unimportant; its
detailed design seemed to affect the rate rather than the fact of
convergence.
	The key idea behind a combinatorial analysis is that the
population of interconnected processors is split up into ε1rε0
sub-populations, each of which obeys the same statistical laws. Formulae
can then be derived for the probabilistic behaviour of each population,
and one can examine the conditions under which the probabilities for
populations that are "on" in the goal state tend to one, and that
of those that are "off" in the goal state tend to zero. The difficulty
in generalizing this proof technique is that choice of the populations
depends upon the structure of ε1Lε0, and so at first sight this way of
proving convergence depends upon ε1Lε0, and therefore has to be
computed anew for each new ε1Lε0.
	This is however not quite true. The way in which the processor
population must be subdivided does depend on ε1Lε0, but not very
sensitively. One can therefore obtain quite general results by studying
what features of ε1Lε0 are important for the subdivision. For the
different numerical values of these features, one can then compute
tables that exhibit the convergence properties for those values, so that
when faced with a new ε1Lε0, one simply derives the values that obtain
for that ε1Lε0, and looks up the convergence region for them rather as one
would look up the value of a cosine.
	This article carries out such a study for a small class of
operators ε1Lε0. The class of all algorithms of the form (1) form a
Turing universal machine (e.g. J. H. Conway's "Life" can be expressed this
way, and Life is known to be Turing-universal), so one cannot hope to examine
convergence for all situations in a single theory. Nevertheless, the
class that we examine here includes all cases that we have actually had
cause to implement, and so it is of some practical usefulness.

.center
ε2Restrictions on the nature of L and of ε3sε0
	 


.end
ββββ